DROPS

Document

Artifact

A Self-Dual Distillation of Session Types: Mechanized Proofs (Artifact)

Authors: Jules Jacobs

Published in: DARTS, Volume 8, Issue 2, Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract

This is the artifact description for the paper "A Self-Dual Distillation of Session Types". The artifact consists of mechanized proofs of the theorems listed in the paper, in the Coq proof assistant.

Cite as

Jules Jacobs. A Self-Dual Distillation of Session Types: Mechanized Proofs (Artifact). In Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 2, pp. 15:1-15:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{jacobs:DARTS.8.2.15,
  author =	{Jacobs, Jules},
  title =	{{A Self-Dual Distillation of Session Types: Mechanized Proofs (Artifact)}},
  pages =	{15:1--15:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{2},
  editor =	{Jacobs, Jules},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.8.2.15},
  URN =		{urn:nbn:de:0030-drops-162137},
  doi =		{10.4230/DARTS.8.2.15},
  annote =	{Keywords: Linear types, concurrency, lambda calculus, session types}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2022.23

A Self-Dual Distillation of Session Types

Authors: Jules Jacobs

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract

We introduce ƛ ("lambda-barrier"), a minimal extension of linear λ-calculus with concurrent communication, which adds only a single new fork construct for spawning threads. It is inspired by GV, a session-typed functional language also based on linear λ-calculus. Unlike GV, ƛ strives to be as simple as possible, and adds no new operations other than fork, no new type formers, and no explicit definition of session type duality. Instead, we use linear function function type τ₁ -∘ τ₂ for communication between threads, which is dual to τ₂ -∘ τ₁, i.e., the function type constructor is dual to itself. Nevertheless, we can encode session types as ƛ types, GV’s channel operations as ƛ terms, and show that this encoding is type-preserving. The linear type system of ƛ ensures that all programs are deadlock-free and satisfy global progress, which we prove in Coq. Because of ƛ’s minimality, these proofs are simpler than mechanized proofs of deadlock freedom for GV.

Cite as

Jules Jacobs. A Self-Dual Distillation of Session Types. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jacobs:LIPIcs.ECOOP.2022.23,
  author =	{Jacobs, Jules},
  title =	{{A Self-Dual Distillation of Session Types}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.23},
  URN =		{urn:nbn:de:0030-drops-162518},
  doi =		{10.4230/LIPIcs.ECOOP.2022.23},
  annote =	{Keywords: Linear types, concurrency, lambda calculus, session types}
}

Search Results

Documents authored by Jacobs, Jules

A Self-Dual Distillation of Session Types: Mechanized Proofs (Artifact)

Abstract

Cite as

A Self-Dual Distillation of Session Types

Abstract

Cite as

Thanks for your feedback!

Could not send message